1. Field of the Invention
This invention relates to a pseudorandom number generator, and more particularly to a pseudorandom number generator which is used to generate a pseudorandom number in a cryptographic communication apparatus or a like apparatus.
2. Description of the Related Art
In communication systems for telephone, data communication or television broadcasting, a crypro-graphic communication apparatus has been used so that transmission information may not be wiretapped by a third party. In the cryptographic communication apparatus, a pseudorandom number is generated using a pseudorandom number generator and added to transmission information by an exclusive OR operation to encipher the transmission information. One of known pseudorandom number generator employs a linear feedback shift register as disclosed, for example, in Japanese Patent Laid-Open No. Heisei 2-90320 (JP, A, 2-90320).
An example of the construction of a conventional pseudorandom number generator is shown in FIG. 1. The pseudorandom number generator 20 is a known apparatus constituted only from a linear feedback shift register and disclosed in various documents including, for example, Solomon W. Golomb, Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales, "Shift Register Sequence (Revised Edition)," Aegean Park Press, 1982 or EiJi Okamoto, "Introduction to Cryprograph Theory," Kyoritsu Shuppan Kabushiki Kaisha, 1993.
The linear feedback shift register or pseudorandom number generator 20 shown in FIG. 1 includes a shift register 21 having a length of L bits and an exclusive OR circuit 22. The shift register 21 is connected to an initial value input terminal 23, a mode control signal input terminal 24 and a clock input terminal 25, and the series input terminal of the shift register 21 is connected to the output terminal 26 of the exclusive OR circuit 22. The initial input terminal 23 has a width of L bits and is used to preset an initial value to the shift register 21. Further, a predetermined one or plurality of ones of column outputs (parallel outputs) of the shift register 21 are connected to input terminals of the exclusive OR circuit 22. The exclusive OR circuit 22 outputs "1" or "0" depending upon whether the number of those inputs which have the value "1" is an odd number or an even number, respectively.
The shift register 21 stores an initial value of the L-bit width inputted from the initial value input terminal 23 in synchronism with a clock pulse signal CLK inputted from the clock input terminal 25 when the mode control signal MODE inputted from the mode control signal input terminal 24 is "1." When the mode control signal MODE is "0," each time the clock pulse signal CLK is inputted, the shift register 21 shifts its stored bit string by one bit rightwardly and stores a signal appearing at the series input terminal into the bit at the left end.
When the pseudorandom number generator (linear feedback shift register) 20 is used, an L-bit random number to be used as an initial value is first supplied to the initial value input terminal 23 and the mode control signal MODE is set to "1," and a clock pulse signal CLK is supplied so that the random number is stored as an initial value into the shift register 21.
In order to generate a pseudorandom number, the mode control signal MODE is changed to "0" and a clock signal is supplied to the clock terminal 25. As a result, each time a clock pulse is inputted, the L-bit information stored in the shift register 21 is shifted as a whole by one bit rightwardly, whereupon one bit at the right end is abandoned, while an output signal of one bit of the exclusive OR circuit 22 is stored into the one bit at the left end of the shift register. The output bit stream of the exclusive OR circuit 22 is then outputted as a pseudorandom number to the outside by way of the output terminal 26.
The pseudorandom number generator shown in FIG. 1 is a so-called M sequence generation circuit and is disadvantageous in that the thus-produced pseudorandom numbers are unsatisfactory in random degree and in that, if some of pseudorandom number series are discovered, an initial state of the linear feedback shift register can be readily presumed by establishing a linear equation, thereby allowing a third party to decipher the cryprograph.
Therefore, another generator has been developed wherein, as shown in FIG. 2, a plurality of linear feedback shift registers are prepared and outputs of the feedback shift registers are coupled by a nonlinear function circuit to obtain a pseudorandom number. The pseudorandom number generator 30 is disclosed in various documents including, for example, Philip R. Geffe, "How to protect data with ciphers that are really hard to break," Electronics, Jan. 4, 1973, pp. 99-101, or the above-mentioned book by Eiji Okamoto. The pseudorandom number generator 30 includes a plurality of linear feedback shift registers 31.sub.1 to 31.sub.n and a nonlinear function circuit 32 which couples output signals of the feedback shift registers 31.sub.1 to 31.sub.n and outputs a resulting signal as a pseudorandom number to an output terminal 36. While the construction of each of the linear feedback shift registers 31.sub.1 to 31.sub.n is similar to that of the linear feedback shift register (pseudorandom number generator 20) shown in FIG. 1, the shift registers do not necessarily have an equal length. Here, the register lengths of the linear feedback shift registers 31.sub.1 to 31.sub.n are L.sub.1 bits . . . , and L.sub.n bits, respectively. For the linear feedback shift registers 31.sub.1 to 31.sub.n, an initial value input terminal 33 for presetting an initial value, a mode control signal input terminal 34 to which a mode control signal MODE is inputted and a clock input terminal 36 to which a clock pulse signal CLK is inputted are provided in common.
The nonlinear function circuit 32 provides an output whose relationship to the input cannot be represented sufficiently only by exclusive OR, and may be constructed from a logic circuit or in the form of a look-up table using a read only memory (ROM). FIG. 3 shows an example of the construction of the nonlinear function circuit 32 constituted from a 3-input logic circuit where three linear feedback shift registers are provided (n=3).
Referring to FIG. 3, the nonlinear function circuit 32 includes a pair of 2-input AND circuits 321 and 323, an inverter circuit 322 and a 2-input OR circuit 324. The first AND circuit 321 inputs output bit streams of the first and second linear feedback shift registers by way of input terminals 325 and 326 and outputs the AND of them. The inverter 322 inputs the output bit stream of the second linear feedback shift register inputted by way of the input terminal 326, logically inverts the bit stream and outputs a resulting bit stream. The second AND circuit 323 inputs an output bit stream of the third linear feedback shift register inputted by way of a further input terminal 327 and the bit stream from the inverter 322 and outputs the AND of the inputted bit streams. The OR circuit 324 logically ORs the output bit streams from the AND circuits 321 and 323 and outputs the OR signal between them to the outside by way of an output terminal 328.
When a pseudorandom number is to be generated using the pseudorandom number generator 30 shown in FIG. 2, random numbers of L.sub.1 bits, L.sub.2 bits , . . . and L.sub.n bits are first supplied as initial values to the linear feedback shift registers 31.sub.1 to 31.sub.n, respectively, by way of the initial value input terminal 33, and the mode control signal MODE of "1" is inputted to the linear feedback shift registers 31.sub.1 to 31.sub.n by way of the mode control signal input terminal 34. Further, a clock pulse signal CLK is supplied by way of the clock input terminal 35 so that the initial values are stored into the linear feedback shift registers 31.sub.1 to 31.sub.n in synchronism with the clock pulse signal CLK. Then, the mode control signal MODE is changed to "0" and a clock signal is inputted by way of the clock input terminal 35 so that, similarly as in FIG. 1, a pseudorandom number stream is outputted serially from the linear feedback shift registers 31.sub.1 to 31.sub.n. The nonlinear function circuit 32 couples the output bit streams from the linear feedback shift registers 31.sub.1 to 31.sub.n with a nonlinear function to finally produce a pseudorandom number and outputs the pseudorandom number to the output terminal 36.
Since the pseudorandom number generator outputs a pseudorandom number obtained by coupling with a nonlinear function, it is difficult to presume initial states of the linear feedback shift registers. However, it is known that, when the pseudorandom number generator is applied to a cryptographic communication apparatus wherein a pseudorandom number is added to transmission data to encipher the transmission data, if there is some deviation in the output distribution when some inputs to the nonlinear function circuit 32 are conditioned, then the enciphered transmission data can be deciphered by a deciphering method known as "correlation attack" or "serial correlation." Details about correlation attack are described in T. Siegenthaler, "Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications." IEEE Transactions on Information Theory, Vol. IT-30, No. 5, pp. 776-780, September 1984, or in the book by Eiji Okamoto mentioned above.
In order to prevent decipherment by correlation attack, the nonlinear function circuit 32 should be designed so that the conditioned output distribution thereof may be uniform when some inputs to the nonlinear function circuit 32 are conditioned. However, where the number of bits of inputs to the nonlinear function circuit 32 is small, for example 3 bits, the conditioned output distribution cannot be made uniform. Accordingly, the pseudorandom number generator 30 of the construction wherein the outputs of the plurality of linear feedback shift registers 31.sub.1 to 31.sub.n are coupled by the nonlinear function circuit 32 is disadvantageous in that it is impossible to realize a cryptographic communication apparatus which is small in apparatus scale and safe.
Please note that the conditioned output distribution of the nonlinear function circuit is hereinafter referred to as "conditioned output distribution."